﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0037_MiddleNode : IAlgorithm
    {
        // 876. 链表的中间结点

        // 给定一个头结点为 head 的非空单链表，返回链表的中间结点。

        // 如果有两个中间结点，则返回第二个中间结点。

        // 提示：
        //  给定链表的结点数介于 1 和 100 之间。

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        // hashmap
        public ListNode MiddleNode(ListNode head)
        {
            var map = new Dictionary<int, ListNode>();
            int i = 1;
            while(head != null)
            {
                map.Add(i++, head);
                head = head.next;
            }
            return map[map.Keys.Count / 2 + 1];
        }

        // 双指针，快慢指针，慢走1，快走2，快走到头，慢就在中间了（实现略）
    }
}
